/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 18
 * Time: 14:20
 */
//力扣106. 从中序与后序遍历序列构造二叉树
class Solution {
    int postIndex;
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex = postorder.length - 1;
        return buildTreeF(postorder, inorder, 0, inorder.length - 1);
    }
    private TreeNode buildTreeF(int[] postorder, int[] inorder, int ib, int ie) {//在inorder(中序遍历)的ib~ie下标中找postorder(后序遍历)相对应的节点然后创建这个根
        if(ib > ie) {//这个条件加在这里
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int inIndex = find(inorder, ib, ie, postorder[postIndex]);
        postIndex--;
        //因为在后序遍历序列中postIndex是自减，所以创建的顺序是先创建根，再创建右树，后创建左树
        root.right = buildTreeF(postorder, inorder, inIndex + 1, ie);//注意是赋给root.left
        root.left = buildTreeF(postorder, inorder, ib, inIndex - 1);//注意是赋给root.right
        return root;
    }
    private int find(int[] inorder, int ib, int ie, int key) {
        for(int i = 0; i <= ie; i++) {//条件是<=，因为buildTreeF传ie的时候传的是inorder.length-1
            if(inorder[i] == key) {
                return i;
            }
        }
        return -1;
    }
}